package com.atwy.graph.sp;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 关键点：多去理解这个关键点及框架， 同时要跳出这个框架，每个关键点都是可以拓展 思路的
 * 备忘录，bp表 int[] distTo
 * 1.初始化，int[] distTo 以及 定义一个 PriorityQueue<State> pq
 * 2.State 类的定义，包括结点标识 和 与起始点的 距离（不要仅仅理解为距离，可以是任意权重的概念）
 * 3.如何取相邻结点，进行 BFS遍历
 * 4.从队列取出一个结点， 判断 + 更新相邻结点
 * 5.得到答案
 */
public class Dijkstra {

    List<Integer>[] graph;
    // 方法签名
    // 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
    int[] dijkstra(int start, List<Integer>[] graph){
        this.graph = graph;
        // 结点个数
        int V = graph.length;
        // 记录最短路径的权重，你可以理解为 dp table
        // 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
        int[] distTo = new int[V];
        // 求最小值，所以 dp table 初始化为正无穷
        Arrays.fill(distTo,Integer.MAX_VALUE);
        // base case
        distTo[start] = 0;

        // 定义一个优先队列
        Queue<State> pq = new PriorityQueue<>((a,b)->a.distFromStart - b.distFromStart);

        // 从起点开始进行BFS
        pq.offer(new State(start,0));

        while (!pq.isEmpty()){
            State currentNode = pq.poll();
            int currentId = currentNode.id;
            int currentDistFromStart = currentNode.distFromStart;
            // 已是最小，不需要更新了
            if(currentDistFromStart > distTo[currentId]){
                continue;
            }
            // 当前结点离起点的距离比记录中的小，则可以尝试更新该结点的所有相邻结点
            for (int nextNodeId : adj(currentId)){
                int weight = weight(currentId, nextNodeId);
                int distToNextNode = distTo[currentId] + weight;
                // 当前结点的更新能够使相邻结点得到更小的结果，更新记录
                if(distTo[nextNodeId] > distToNextNode){
                    distTo[nextNodeId] = distToNextNode;
                    pq.offer(new State(nextNodeId, distToNextNode));
                }
            }
        }
        return distTo;
    }

    // 返回节点 from 到节点 to 之间的边的权重
    int weight(int from, int to){
        return this.graph[from].get(to);
    }

    // 输入节点 s 返回 s 的相邻节点
    List<Integer> adj(int s){
        return this.graph[s];
    }

    /**
     * 记录结点状态，辅助计算
     */
    class State{
        // 当前结点标识，可以是int类型，也可以是一个对象，一个表示二维的点，关键在于标识结点
        int id;
        // 当前结点到起始点的距离（加权距离）
        int distFromStart;
        public State(int id,int distFromStart){
            this.id = id;
            this.distFromStart = distFromStart;
        }
    }
}
